package 剑指offer.双指针法;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

/**
 * 解法：双指针
 * 一个指向开头，一个指向结尾。
 * 若和等于 sum 则退出；
 * 若和小于 sum 则前指针后移一个；
 * 若和大于 sum 则后指针前移一个。
 */
public class 第57题和为S的数字 {

    static class Node implements Comparator<Node> {
        private Integer val1;
        private Integer val2;
        private Integer multiply;

        public Node(Integer v1, Integer v2, Integer m) {
            this.val1 = v1;
            this.val2 = v2;
            this.multiply = m;
        }


        @Override
        public int compare(Node o1, Node o2) {
            return o1.multiply - o2.multiply;
        }
    }

    /**
     * 第一问：和为S的两个数字
     * 输入一个递增数组和一个数字S，在数组中找到两个数字使他们的和等于S，
     * 若存在多组结果输出任意一个即可
     * @param array
     * @param sum
     * @return
     */
    public static ArrayList<Integer> FindNumbersWithSum(int[] array, int sum) {
        ArrayList<Node> ans = new ArrayList<>();
        for (int i = 0; i < array.length; i++) {
            for (int j = i + 1; j < array.length; j++) {
                if ((array[i] + array[j]) == sum) {
                    ans.add(new Node(array[i], array[j], array[i] * array[j]));
                }
            }
        }
        ArrayList<Integer> res = new ArrayList<>();
        if (ans.size() != 0) {
            res.add(ans.get(0).val1);
            res.add(ans.get(0).val2);
            Collections.sort(res);
        }
        return res;
    }


    public static void main(String[] args) {
//        ArrayList<Integer> ans = FindNumbersWithSum(new int[]{1, 2, 4, 7, 11, 15}, 15);
//        ArrayList<Integer> ans = FindNumbersWithSum(new int[]{1, 2, 4, 7, 11, 16}, 10);
//        ArrayList<Integer> ans = FindNumbersWithSum(new int[]{1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20}, 21);
//        ans.forEach(e -> System.out.println(e));



        // 测试第二问
        FindContinuousSequence(9).forEach(e -> System.out.println(e));
    }


    /**
     * 第二问：和为S的连续正数序列
     *
     * 使用双指针法：首先让p1指向1，p2指向2。然后计算指针之和，
     * 若和小于 sum 说明p2需要扩大，若和大于 sum 说明 p1 需要扩大
     * 若和等于 sum 说明需要把p1至p2之间的数据全部加入到集合中，这是一组解。
     * 接着扩大p2继续往下求解
     */
    public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        // 先建立左右指针，指向两个初始值
        int start = 1;
        int end = 2;
        // 排除特殊情况
        if (sum < 3)
            return ans;
        // start 和 end 不会 >= sum
        // start 也不会大于 sum 的一半
        int currentSum = start + end;
        while (start <= sum / 2) {
            // 将符合要求的集合添加到 ans 里面
            if (currentSum == sum) {
                ArrayList<Integer> l = new ArrayList<>();
                for (int i = start; i <= end; i++) {
                    l.add(i);
                }
                ans.add(l);
                // 将窗口扩大，遍历接下来的元素
                end++;
                currentSum += end;
                continue;
            }
            // 如果不符合，一定是 currentSum 小了，需要增大 end
            if (currentSum < sum) {
                end++;
                currentSum += end;
                continue;
            }
            if (currentSum > sum) {
                currentSum -= start;
                start++;
                continue;
            }
        }
        return ans;
    }
}
